package com.zjj.algorithm.learning.dmsxl.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 代码随想录算法学习，二叉树。
 * 第一讲：二叉树的递归遍历
 *
 * @author zjj_admin
 * @date 2022/12/22 10:04
 */
public class Tree_01_RecursiveTraversal {

    public static void main(String[] args) {


        /**
         *            node1
         *      node2
         *  node3    node4
         *          node5
         *        node6
         */
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);

        node1.left = node2;
        node2.left = node3;
        node2.right = node4;
        node4.left = node5;
        node5.left = node6;

        List<Integer> res1 = new ArrayList<>();
        preOrder(node1, res1);
        //res1 = [1, 2, 3, 4, 5, 6]
        System.out.println("res1 = " + res1);

        List<Integer> res2 = new ArrayList<>();
        midOrder(node1, res2);
        //res2 = [3, 2, 6, 5, 4, 1]
        System.out.println("res2 = " + res2);

        List<Integer> res3 = new ArrayList<>();
        postOrder(node1, res3);
        //res3 = [3, 6, 5, 4, 2, 1]
        System.out.println("res3 = " + res3);


    }


    /**
     * 二叉树的前序遍历，使用递归的方法
     *
     * @param root
     * @param res
     */
    public static void preOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //前序遍历时，首先遍历当前节点，再遍历当前节点的左子节点，最后遍历当前节点的右子节点
        res.add(root.val);
        preOrder(root.left, res);
        preOrder(root.right, res);
    }


    public static void midOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        //前序遍历时，首先遍历当左子节点，再遍历当前节点，最后遍历当前节点的右子节点
        midOrder(root.left, res);
        res.add(root.val);
        midOrder(root.right, res);
    }


    /**
     * 二叉树后序递归遍历
     * @param root
     * @param res
     */
    public static void postOrder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postOrder(root.left, res);
        postOrder(root.right, res);
        res.add(root.val);
    }
}
